The present invention relates to arrays for performing logic functions and more particularly it is related to increasing the number of logic functions performed in an array without increasing the size of the array.
The performing of logic in matrices of identical circuit elements each located at a unique intersection of an input and output line in a grid of intersecting input and output lines is well known. It is also well known that the standardization of logic circuit layouts stemming from the use of logic matrices or arrays results in the simplification and acceleration of the design and manufacturing of monolithic chips containing logic performing circuits. However, up until now the use of the logic arrays has been limited. A major cause in this limited use has been that only a small percentage of the intersections in an array turn out to be usable in performing logic functions. This percentage of useful intersections in the arrays results in inefficient use of the surface area of the monolithic chips on which the arrays are fabricated. It turns out, that for most applications, the design and manufacturing efficiencies of logic arrays are outweighed economically by their inefficient use of chip area and it is less expensive to spend additional time and effort to design and manufacture logic chips with highly customized layouts that are less orderly than logic arrays but perform far more logic functions in a given area of a monolithic chip.
The small percentage of usable logic circuits in a logic array is a result of the orderliness of the array. Once input and output lines are used to perform a given logic function they cannot be used in performing other unrelated logic functions without hopelessly garbling the logic. As a result large areas of the array contain intersections of input and output lines that are barren of usable circuits.
A number of schemes have been devised to reduce the sparceness of the logic on logic array chips. One such scheme is to use a plurality of decoders to feed input variables to the input lines of a single array allowing a number of very powerful logic functions to be efficiently performed in a single array. Another scheme used to reduce sparseness involves using compound arrangements of arrays called programmable array logic chips (PLAs). These involve feeding the output of a first array called a product term generator, a search table or an AND array, to a second array called the sum of a product term generator, a readout table or an OR array, so as to increase the number of functions that can be performed without geometrically increasing the number of array intersections needed to perform those functions. While these modifications increase the number of useful logic circuits that can be placed in an array logic chip, they do not solve the problem of the unusable portions of the input and output lines that is discussed above.